// https://www.lintcode.com/problem/valid-anagram/description
// 158. 两个字符串是变位词
// 写出一个函数 anagram(s, t) 判断两个字符串是否可以通过改变字母的顺序变成一样的字符串。

// 样例
// 给出 s = "abcd"，t="dcab"，返回 true.
// 给出 s = "ab", t = "ab", 返回 true.
// 给出 s = "ab", t = "ac", 返回 false.

// 挑战
// O(n) 的时间复杂度, O(1) 的额外空间

// 说明
// 什么是 Anagram?

// 在更改字符顺序后两个字符串可以相同



class Solution {
public:
    /**
     * @param s: The first string
     * @param t: The second string
     * @return: true or false
     */
   
    bool anagram(string &s, string &t) {
         // 法一：map
        // map<char, int> char_map;
        // for (int i = 0; i < s.length(); i++)
        // {
        //     char_map[s[i]]++;
        // }
        // for (int i = 0; i < t.length(); i++)
        // {
        //     if (char_map.find(t[i]) == char_map.end())
        //     {
        //         return false;
        //     }
        //     else
        //     {
        //         char_map[t[i]]--;
        //     }
        // }
        // for (map<char, int>::iterator iter = char_map.begin(); iter != char_map.end(); ++iter)
        // {
        //     if(iter->second != 0)
        //     {
        //         return false;
        //     }
        // }
        // return true;
        
        // 法二：一个数组map
        // char char_map[256] = {0};
        // for (int i = 0; i < s.length(); i++)
        // {
        //     char_map[s[i]]++;
        // }
        // for (int i = 0; i < t.length(); i++)
        // {
        //     char_map[t[i]]--;
        // }
        // for (int i = 0; i < 256; i++)
        // {
        //     if (char_map[i] != 0)
        //     {
        //         return false;
        //     }
        // }
        // return true;
        
        // 法三：两个数组
        // char char_map_s[256] = {0};
        // char char_map_t[256] = {0};
        // for (int i = 0; i < s.length(); i++)
        // {
        //     char_map_s[s[i]]++;
        // }
        // for (int i = 0; i < t.length(); i++)
        // {
        //     char_map_t[t[i]]++;
        // }
        // for (int i = 0; i < 256; i++)
        // {
        //     if (char_map_s[i] != char_map_t[i])
        //     {
        //         return false;
        //     }
        // }
        // return true;
        
        // 法四：排序
        sort(s.begin(), s.end());
        sort(t.begin(), t.end());
        return t == s;
    }
};